package org.algorithm.biubiu.wheel_1.数组.三月.第四周;

/**
 * @author zhx
 * @version 1.0
 * @date 2022/03/24 8:35 PM
 * @description:  周六
 *
 * url:  https://leetcode-cn.com/problems/search-rotate-array-lcci/
 *
 * //TODO  need review 二分之 奇葩
 */
public class 搜索旋转数组 {

    public static void main(String[] args) {


        int[] arr = {1,-2};
        System.out.println(search(arr, -2));
    }


    public static int search(int[] arr, int target) {
        //2分发
        if(arr[0]==target) return 0;
        int left = 0;
        int right = arr.length-1;
        while(left<=right){

            int mid = left + (right-left)/2;
            if(arr[mid]==target){
                while(mid>0&&arr[mid-1]==arr[mid])  mid--;
                return  mid;
            }
            else if(arr[mid]<arr[right]){
                if(arr[mid]<target && target<=arr[right]){
                    left = mid+1;
                }else{
                    right = mid-1;
                }
            }
            else if(arr[mid]>arr[right]){
                if(arr[left]<=target&& target< arr[mid]){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
            }
            else{
                right--;
            }
        }
        return -1;
    }
}
